﻿//

//给定一个
//�
//×
//�
//
//n×m  的网格，其中每个单元格中可能有三种值中的一个 0, 1, 2。
//其中 0 表示这个格子为空、1 表示这个格子有一个完好的苹果，2 表示这个格子有一个腐烂的苹果。
//腐烂的苹果每分钟会向上下左右四个方向的苹果传播一次病菌，并导致相邻的苹果腐烂。请问经过多少分钟，网格中不存在完好的苹果。如果有苹果永远不会腐烂则返回 - 1
//数据范围：
//0≤val≤2
//示例1
//输入：
//[[2, 1, 1], [1, 0, 1], [1, 1, 1]]
//复制
//返回值：
//4
//复制
//示例2
//输入：
//[[2, 1, 0], [1, 0, 1], [0, 0, 0]]
//复制
//返回值：
//- 1





//思路：这里虽然是bfs有两种思路的方向可以让我们完成代码的操作，一个就是递归，另一个就是迭代，这里考虑一下迭代完成，
//即通过选择合容器配合出入以及循环完成。下面讲解一下迭代应用于本题的具体思路：

//1.首先这道题就是我们先遍历数组然后找到所有的2，之后在同时从每个2开始上下左右找1覆盖成2并记录位置，并把它们就录下来方便下次用，第一批2用完后，这时是过去了一分钟故用个计时器记录一下，然后拿到刚刚保存的那些2重复操作即可，最后呢要么里面还有1没有被修改要么就是2和0了，这里如果有1那么就返回-1，否则返回这个计时器记录的就可。

//2·思路的进一步转化：由上面的思路，如保存一些2的位置然后后面还要添加方便再一次使用，很容易想到队列，这里还有两个要处理
//如何控制它每次都是用完保存的第一批然后再用第二批，那么此时可以用一个size记录第一批长度然后再入第二批，依次对size减减，另一个就是什么时候开始计时？ 根据题意我们可以知道每次的同一批2是同时查找的故这就是一分钟，因此一批过后才计数器加加。

//当然这里还有一个更细节问题需要处理就是我们的计时器：先说结论这里计时器count，如果找不到1，那么应该返回的是cout-1；为什么呢？这里不是，每次队列里每减完一批2所在位置那么count就加加，我们可以根据例1推算出，结论：当走到最后的那批，此时这批是无法找到再下一批的但是还会使得count++，故这次应该不算，但是我们把它算进去了，故应该减去。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param grid int整型vector<vector<>>
     * @return int整型
     */
    queue<pair<int, int>>q;
    int count = 0;
    //这里写一个函数判断下标是否越界问题：
    bool judge(vector<vector<int> >& grid, int m, int n) {
        if (m < 0 || m >= grid.size() || n < 0 || n >= grid[0].size()) return false;
        else return true;

    }
    //子函数利用容器特点把递归转换成迭代解决：
    void bfs(vector<vector<int> >& grid, int& count) {

        while (!q.empty()) {
            int size = q.size();
            while (size--) {
                pair<int, int> f = q.front();
                q.pop();
                int i = f.first;
                int j = f.second;
                if (judge(grid, i, j - 1) && grid[i][j - 1] == 1) {
                    q.push(make_pair(i, j - 1));
                    grid[i][j - 1] = 2;
                }
                if (judge(grid, i, j + 1) && grid[i][j + 1] == 1) {
                    q.push(make_pair(i, j + 1));
                    grid[i][j + 1] = 2;
                }
                if (judge(grid, i - 1, j) && grid[i - 1][j] == 1) {
                    q.push(make_pair(i - 1, j));
                    grid[i - 1][j] = 2;
                }
                if (judge(grid, i + 1, j) && grid[i + 1][j] == 1) {
                    q.push(make_pair(i + 1, j));
                    grid[i + 1][j] = 2;
                }



            }
            count++;
        }
    }

    int rotApple(vector<vector<int> >& grid) {
        // write code here
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == 2) {
                    q.push(make_pair(i, j));
                }

            }
        }
        bfs(grid, count);
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == 1) return -1;



            }
        }
        return count - 1;

    }
};